#region Copyright Notice
// 
// 
//  
//  Copyright (c) 2009-2011 Anindya Chatterjee
//  
//  Licensed under the Apache License, Version 2.0 (the "License");
//  you may not use this file except in compliance with the License.
//  You may obtain a copy of the License at
//  
//      http://www.apache.org/licenses/LICENSE-2.0
//  
//  Unless required by applicable law or agreed to in writing, software
//  distributed under the License is distributed on an "AS IS" BASIS,
//  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//  See the License for the specific language governing permissions and
//  limitations under the License.
// 
// 
#endregion
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using AbstractClass.Linq;

namespace AbstractClass.Collections.Generic
{
    /// <summary>
    /// Represents an abstract tree data structure.
    /// </summary>
    /// <typeparam name="T">The type of the values in the tree.</typeparam>
    /// <typeparam name="TNode">The type of the nodes in the tree.</typeparam>
    [Serializable, DebuggerDisplay("Root = {Root.Value}")]
    public abstract class AbstractTree<T, TNode> where TNode : AbstractNode<T>, new()
    {
        /// <summary>
        /// Initializes a new instance of the <see cref="AbstractTree&lt;T, TNode&gt;"/> class.
        /// </summary>
        protected AbstractTree()
        {
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="AbstractTree&lt;T, TNode&gt;"/> class.
        /// </summary>
        /// <param name="root">The root node of this instance.</param>
        protected AbstractTree(TNode root)
        {
            Root = root;
            Root.Parent = null;
        }

        /// <summary>
        /// Gets the leaf nodes of the tree.
        /// </summary>
        /// <value>The leaf nodes.</value>
        public abstract IEnumerable<TNode> Leaves { get; }

        /// <summary>
        /// Gets all nodes in the tree.
        /// </summary>
        /// <value>The nodes in the tree.</value>
        public abstract IEnumerable<TNode> ToEnumerable { get; }

        /// <summary>
        /// Gets the node count of the tree.
        /// </summary>
        /// <value>The node count.</value>
        public int Count
        {
            get
            {
                if (ToEnumerable == null)
                {
                    return 0;
                }
                return ToEnumerable.Count();
            }
        }

        /// <summary>
        /// Gets the height of the tree.
        /// </summary>
        /// <value>The height of the tree.</value>
        public int Height
        {
            get { return !Leaves.IsNullOrEmpty() ? Leaves.Max(x => x.Depth) : 0; }
        }

        /// <summary>
        /// Gets or sets the root node of the current instance.
        /// </summary>
        /// <value>The root node.</value>
        public TNode Root { get; set; }

        /// <summary>
        /// Adds the node to the tree.
        /// </summary>
        /// <param name="node">The node to add.</param>
        /// <returns>
        /// <c>true</c> if added successfully; otherwise, <c>false</c>.
        /// </returns>
        public abstract bool AddNode(TNode node);

        /// <summary>
        /// Adds the node to the tree.
        /// </summary>
        /// <param name="node">The node to add.</param>
        /// <param name="depth">The depth at which the node to be attached.</param>
        /// <returns>
        /// <c>true</c> if added successfully; otherwise, <c>false</c>.
        /// </returns>
        public abstract bool AddNode(TNode node, int depth);

        /// <summary>
        /// Deletes the node from the tree.
        /// </summary>
        /// <param name="node">The node to delete.</param>
        /// <returns>
        /// <c>true</c> if deleted successfully; otherwise, <c>false</c>.
        /// </returns>
        public abstract bool DeleteNode(TNode node);

        /// <summary>
        /// Tries to get the node specified by <paramref name="data"/> from the tree.
        /// </summary>
        /// <param name="data">The data to search.</param>
        /// <returns>
        /// <typeparamref name="TNode" /> if fetching successful; otherwise, <c>null</c>.
        /// </returns>
        public abstract TNode TryGetNode(T data);

        /// <summary>
        /// Determines whether the specified <paramref name="node"/> is in the tree or not.
        /// </summary>
        /// <param name="node">The node to find.</param>
        /// <returns>
        /// 	<c>true</c> if the tree has the specified node; otherwise, <c>false</c>.
        /// </returns>
        public abstract bool HasNode(TNode node);

        /// <summary>
        /// Clears this instance and remove all the nodes attached to it.
        /// </summary>
        public abstract void Clear();

        /// <summary>
        /// Gets the sub-tree rooted at <paramref name="node"/>.
        /// </summary>
        /// <param name="node">The root node of the sub-tree.</param>
        /// <returns>
        /// A <see cref="AbstractTree&lt;T, TNode&gt;" /> object with <paramref name="node"/> at its root.
        /// </returns>
        public abstract AbstractTree<T, TNode> GetSubtree(TNode node);

        /// <summary>
        /// Creates a clone of this instance.
        /// </summary>
        /// <returns>
        /// A new <see cref="AbstractTree&lt;T, TNode&gt;" /> object, which is a clone of this instance.
        /// </returns>
        public abstract AbstractTree<T, TNode> Clone();

        /// <summary>
        /// Creates a node with the value specified and adds to the tree.
        /// </summary>
        /// <param name="value">The value to add.</param>
        /// <returns>
        /// <c>true</c> if added successfully; otherwise, <c>false</c>.
        /// </returns>
        public virtual bool AddNode(T value)
        {
            return AddNode(value, -1);
        }

        /// <summary>
        /// Creates a node with the value specified and adds to the tree at a specified depth.
        /// </summary>
        /// <param name="value">The value to add.</param>
        /// <param name="depth">The depth to add at.</param>
        /// <returns>
        /// <c>true</c> if added successfully; otherwise, <c>false</c>.
        /// </returns>
        public virtual bool AddNode(T value, int depth)
        {
            var node = new TNode {Value = value};
            return AddNode(node, depth);
        }

        /// <summary>
        /// Deletes the node from the tree.
        /// </summary>
        /// <param name="data">The data associated with the node.</param>
        /// <returns>
        /// <c>true</c> if deleted successfully; otherwise, <c>false</c>.
        /// </returns>
        public virtual bool DeleteNode(T data)
        {
            TNode node = TryGetNode(data);
            return node != null && DeleteNode(node);
        }

        /// <summary>
        /// Determines whether the node specified by the <paramref name="data"/> is in the tree.
        /// </summary>
        /// <param name="data">The data to search.</param>
        /// <returns>
        /// 	<c>true</c> if the specified data has node; otherwise, <c>false</c>.
        /// </returns>
        public virtual bool HasNode(T data)
        {
            TNode node = TryGetNode(data);
            return node != null;
        }

        /// <summary>
        /// Finds the nearest common ancestor of two nodes.
        /// </summary>
        /// <param name="node1">First node.</param>
        /// <param name="node2">Second node.</param>
        /// <returns>The nearest common ancestor node of <paramref name="node1"/> and <paramref name="node2"/>.</returns>
        /// <remarks>
        /// If one of the specified nodes is a descendant of the other, then it returns the parent of the
        /// first one.
        /// </remarks>
        public static TNode LeastCommonAncestor(TNode node1, TNode node2)
        {
            IEnumerable<AbstractNode<T>> path1ToRoot = node1.PathToRoot;
            IEnumerable<AbstractNode<T>> path2ToRoot = node2.PathToRoot;

            IEnumerable<AbstractNode<T>> commonAncestor = path1ToRoot.Intersect(path2ToRoot);
            AbstractNode<T> lca = commonAncestor.First();

            if (lca.Equals(node1) && !lca.IsRoot())
                lca = node1.Parent;
            else if (lca.Equals(node2) && !lca.IsRoot())
                lca = node2.Parent;

            return (TNode) lca;
        }
    }
}